package leetcode.递归回溯BFSDFS;

import java.util.ArrayList;
import java.util.List;

/**
 * 组合总和
 *
 * 数组 candidates 里面的数据不重复，在 candidates 里面找出一些数字
 * 使他们的和等于 target
 *
 * candidates 中的数字可以无限制重复被选取。
 *
 */
public class Test39组合总和 {

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (candidates.length == 0) {
            return res;
        }
        List<Integer> list = new ArrayList<>();
        backTrace(res, list, candidates, target, 0, 0);
        return res;
    }

    public static void backTrace(List<List<Integer>> res, List<Integer> list
            , int[] nums, int target, int sum, int start) {
        if (sum > target)
            return;
        if (sum == target)
            res.add(new ArrayList<>(list));
        else {
            for (int i = start; i < nums.length; i++) {
                list.add(nums[i]);
                sum += nums[i];
                backTrace(res, list, nums, target, sum, i);
                // 让 start 从当前遍历的 i 开始，可以去重。
                // 若下一次递归从 i+1 开始的话意思就是同一个数据不能重复使用
                list.remove(list.size() - 1);
                sum -= nums[i];
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 6, 7};
        int target = 7;
        System.out.println(combinationSum(nums, target));

        // [[2, 2, 2, 2], [2, 3, 3], [3, 2, 3], [3, 3, 2], [3, 5], [5, 3]]
        // 输出这种重复结果的原因就是i不是接着往下走的，每次都从0开始
        // 控制i接着执行而不是从0开始即可
    }

}
